package everydayone.hasPathSum;

import java.util.LinkedList;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @date 2020/07/07
 * @author 王光浩
 * @introduction 采用迭代方式来完成
 * @analysis 时间复杂度O（n），空间复杂度O（n）
 */
public class MyMethodTwo {
	public boolean hasPathSum(TreeNode root, int sum) {
		if (root == null)
			return false;
		LinkedList<TreeNode> nodeStack = new LinkedList<TreeNode>();
		LinkedList<Integer> valueStack = new LinkedList<Integer>();
		nodeStack.offer(root);
		valueStack.offer(sum);
		while (!nodeStack.isEmpty()) {
			TreeNode node = nodeStack.poll();
			int value = valueStack.poll();
			if (node.left == null && node.right == null && node.val == value)
				return true;
			if (node.right != null) {
				nodeStack.add(node.right);
				valueStack.add(value - node.val);
			}
			if (node.left != null) {
				nodeStack.add(node.left);
				valueStack.add(value - node.val);
			}
		}
		return false;
	}
}
